Computers, broadly speaking, are electronic machines capable of storing and manipulating information, often called data, to useful ends. Frequently, a number of computers are connected together in such a way that they are able to send data to each other. A collection of computers so connected is often called a network, and the connector between two network nodes is referred to as a link. One type of computer network is called a LAN (local area network), and may be found, for example, in the offices of a small business or educational institution. A number of LANs or other networks may also be brought into communication with each other. As might be expected, a system of rules or set procedures must be put in place so that the computers and networks can communicate with each other effectively. Such a system of rules and procedures is often called a protocol, and several have been developed for communications involving computer networks.
A widely accepted set of protocols for LAN communications has been developed under the auspices of the IEEE (Institute of Electrical and Electronics Engineers). A standard generally referred to as IEEE 802, for example, covers general network architecture, IEEE 802.1 deals with bridging and management, and IEEE 802.3 is the Ethernet protocol. An Ethernet LAN is one that handles traffic, that is, the flow of data from one computer to one or more other, using a system of collision detection and avoidance. (A ‘collision’ occurs when two or more computers attempt to send data over the same link at the same time.) These standards are regularly reviewed and updated as necessary to improve networks operations and account for developments in technology.
In a typical Ethernet network, data sent from one computer to another, or from one network to another, is not transmitted all at once or continuously, but is instead broken up into discrete ‘frames’. The frames may vary in length, but each frame includes sufficient address information (in addition to the actual data) so it they may be routed to its desired destination or destinations. Routing is necessary because every computer is not connected directly to every other. Instead, computers and networks are connected to intermediary devices that receive data, determine its destination address, and then route it accordingly. One such intermediary device is referred to as a bridge. A bridge is a type of software switch resident on a network component. A frame of data may be routed through many bridges on its way from source to destination.
FIG. 3 is a simplified schematic diagram illustrating the bridges of an exemplary network 10, in which embodiments of the present invention may be advantageously implemented. The network may have many components, but for clarity only the bridges themselves are shown. Individual components such as computers and sub-networks may be connected to one of the bridges. In the embodiment of FIG. 3, there are nine bridges, numbered 1 through 9, although the present invention is also suitable for implementation in larger or smaller networks. Each of these bridges 1 through 9 is connected by a link to one or more other bridges. In FIG. 15 the links are numbered according to the bridges it connects, for example link 24 connects bridge 2 with bridge 4. When a bridge receives a data frame from, for example, a network computer or another bridge, it examines the address information and forwards the frame accordingly. Data may have to pass through several bridges from its source to destination. Without some governing protocol, however, it is possible that frames of data might inadvertently be sent from bridge to bridge, eventually looping back to a previously-visited bridge from which they are re-sent back into the same loop. As should be apparent, this is not a desirable phenomenon and techniques have evolved for avoiding this looping problem.
One technique to avoid looping would be to use a fixed-configuration network and always route frames intended for a particular destination by the same route. Most networks are subject to change, however, and occasionally encounter failures in components and links. A static routing system is therefore not the best solution. In a more successful solution, a ‘spanning tree’ is calculated periodically according to a spanning tree protocol (STP). The spanning tree provides path definitions for the network as it exists at the time of the tree calculation. In the event of a failure or other event, the tree can be recalculated to adjust to the new conditions.
In Shortest Path Bridging (SPB), specified for example in IEEE 802.1aq Virtual Bridged Local Area Networks—Amendment 9: Shortest Path Bridging, Draft D0.3, May 9, 2006, an attempt is made to provide the shortest path between any two bridges of and Ethernet network. In this proposed solution, each bridge maintains a separate tree. (Or at least each ‘edge bridge’; bridges that connect only to other bridges and not to any other device may not form the root of their own tree.) Frames of data arriving at a bridge directly from an end station are forwarded from the bridge to the bridge's tree, in which it is the root bridge.
The current SPB proposal is based on the path vector approach. The path vector scheme allows any two bridges to choose symmetrical paths between them, which are required for the MAC (media access control) learning process to work correctly. The path vector approach provides the shortest path (that is, the one with the least administrative cost) between any two bridges. It provides only the shortest path, however, meaning that other objectives cannot be considered even if that would be desirable. And since MAC learning is applied for the multiple spanning trees associated with the various bridges, different convergence times for the different trees may result. This produces a temporal inconsistency that may result in excessive broadcasting. It is believed, however, that recovery time could be improved if the path vector approach could be replaced with a link state approach.
In general, the link state approach, using routing protocols such as OSPF (open shortest path first) and IS-IS (intermediate system to intermediate system), facilitates application of traffic engineering and allows the active topology to be optimized. Directly implementing these IP routing protocols, however, would mean each bridge would have to set up its own forwarding tables. This procedure is not a detriment in and of itself, and could be applied to SPB, but on the other hand it may produce long unavailable periods resulting in at least transient loops. Another complication is that Ethernet frames do not include a TTL (time to live) field (as does an IP packet) so transient loops may be problematic when changes in active topology are occurring. Of course, bridges that notice the topology is changing could simply stop forwarding data frames until a new topology is calculated, but this procedure slows down the recovery significantly.
The convergence time in the currently proposed SPB approach could theoretically be improved by a protection switching scheme where both primary and backup trees are maintained. In practice, however, a single backup tree cannot provide protection against all possible failures, and using multiple backup trees in a system, such as SPB, that requires a tree for each bridge, might significantly or even severely tax system resources.
There is therefore a need in the art for a way to implement a link state approach to support the multiple spanning trees used in SPB. The present invention provides just such a solution.